package main

import (
	"fmt"
)

func main() {
	s := "测试一下字符串"
	substr := "字符"
	fmt.Println(Index(s, substr))
}
func Index(s string, sub string) int {
	s1 := []rune(s)
	s2 := []rune(sub)
	next := make([]int, len(s2))
	getnext(next, s2)
	j := -1
	for i := 1; i < len(s); i++ {
		for j >= 0 && s1[i] != s2[j+1] {
			j = next[i]
		}
		if s1[i] == s2[j+1] {
			j++
		}
		if j == len(s2)-1 {
			return i - len(s2) + 1
		}
	}
	return -1
}

func getnext(next []int, s []rune) {
	j := -1
	next[0] = j
	for i := 1; i < len(s); i++ {
		for j >= 0 && s[i] != s[j+1] {
			j = next[j]
		}
		if s[i] == s[j+1] {
			j++
		}
		next[i] = j
	}
}
